package com.buddy.learn.algorithm.demo;

import java.util.Scanner;

/**
 * @author Buddy
 * @date 2021/5/6
 */
public class _016金明的预算方案 {
    /**
     * 输入的第 1 行，为两个正整数，用一个空格隔开：N m
     * 其中 N （ <32000 ）表示总钱数， m （ <60 ）为希望购买物品的个数。）
     * 从第 2 行到第 m+1 行，第 j 行给出了编号为 j-1 的物品的基本数据，每行有 3 个非负整数 v p q
     * （其中 ：
     * v 表示该物品的价格（ v<10000 ），
     * p 表示该物品的重要度（ 1 ~ 5 ），
     * q 表示该物品是主件还是附件。
     * 如果 q=0 ，表示该物品为主件，如果 q>0 ，表示该物品为附件， q 是所属主件的编号）
     * 输出文件只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（ <200000 ）。
     */

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 总钱数
        int N = scanner.nextInt();
        // 想购买的商品数
        int m = scanner.nextInt();
        if (N <= 0 || m <= 0) {
            System.out.println(0);
        }
        Good[] goods = new Good[m+1];
        for (int i = 1; i <= m; i++) {
            int v = scanner.nextInt();
            int p = scanner.nextInt();
            int q = scanner.nextInt();
            goods[i] = new Good(v, p, q);
            if (q > 0) {
                if (goods[q].a1 == 0) {
                    goods[q].a1 = i;
                } else {
                    goods[q].a2 = i;
                }
            }
        }

        int[][] dp = new int[m + 1][N + 1];
        for (int i = 1; i <= m; i++) {
            int v = 0, v1 = 0, v2 = 0, v3 = 0, tempdp = 0, tempdp1 = 0, tempdp2 = 0, tempdp3 = 0;
            v = goods[i].v;
            //只有主件
            tempdp = goods[i].p * v;
            // 主件 + 附件1
            if (goods[i].a1 != 0) {
                v1 = goods[goods[i].a1].v + v;
                tempdp1 = tempdp + goods[goods[i].a1].v * goods[goods[i].a1].p;
            }
            // 主件 + 附件2
            if (goods[i].a2 != 0) {
                v2 = goods[goods[i].a2].v + v;
                tempdp2 = tempdp + goods[goods[i].a2].v * goods[goods[i].a2].p;
            }

            // 主件 + 附件2
            if (goods[i].a1 != 0 && goods[i].a2 != 0) {
                v3 = goods[goods[i].a1].v + goods[goods[i].a2].v + v;
                tempdp3 = tempdp + goods[goods[i].a1].v * goods[goods[i].a1].p + goods[goods[i].a2].v * goods[goods[i].a2].p;
            }

            for (int j = 1; j <= N; j++) {
                //当物品i是附件时,相当于跳过
                if (goods[i].q > 0) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j];
                    if (j >= v && v != 0) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v] + tempdp);
                    }
                    if (j >= v1 && v1 != 0) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v1] + tempdp1);
                    }
                    if (j >= v2 && v2 != 0) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v2] + tempdp2);
                    }
                    if (j >= v3 && v3 != 0) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v3] + tempdp3);
                    }
                }
            }
        }
        System.out.println(dp[m][N]);
    }

}


class Good {
    /**
     * 物品的价格
     */
    int v;
    /**
     * 物品的重要度
     */
    int p;
    /**
     * 物品的主附件ID
     */
    int q;
    /**
     * 附件1ID
     */
    int a1 = 0;
    /**
     * 附件2ID
     */
    int a2 = 0;

    Good(int v, int p, int q) {
        this.v = v;
        this.p = p;
        this.q = q;
    }
}
